In a communication network node, a network interface controller (NIC) is employed to multiplex incoming and outgoing data stream elements (such as, e.g., packets or cells) associated with multiple communication channels (or "virtual circuits" (VCs)) established within a communication link. For outgoing data elements, the NIC requires a mechanism for arbitrating between the channels and determining the order in which their associated data stream elements are to be transmitted into the network. This arbitration mechanism must take into account various characteristics related to the channels, including, e.g., the service classes of the various data streams and any associated quality of service (QOS) requirements.
The service classes include, e.g., (in decreasing order of priority): Constant Bit Rate (CBR) for real-time data sampled at constant intervals (i.e., data having a constant frame size and a constant "stride" between frames), Real-time Variable Bit Rate (RT.sub.-- VBR) for real-time data that varies in rate and tolerates more jitter (i.e., real-time data having a variable frame size and a constant stride between frames), Non-real-time Variable Bit Rate (N.sub.-- VBR) for data that can tolerate more relaxed timing but requires reserved bandwidth (i.e., non-real-time data having a variable frame size and a variable stride between frames), Available Bit Rate (ABR) for non-real-time flow controlled bursty computer data traffic (i.e., non-real-time data having a variable frame size and a variable stride between frames which utilizes bandwidth (up to a specified maximum) not used by higher priority data traffic), and Unspecified Bit Rate (UBR) for non-flow controlled computer traffic with only a best effort delivery requirement (i.e., non-real-time data having a variable frame size and no guaranteed stride between frames, which utilizes bandwidth not used by higher priority traffic, up to the maximum communication link bandwidth). QOSs are determined by such variables as the minimum and maximum transmission rate, maximum variation in data element spacing, maximum burst length, etc.
With the continued integration by computer applications of more and more multimedia communication with the traditional file transfers, network attached input/output (I/O), and intra-cluster communication, there is increasing pressure on network components to handle simultaneously a large number of data streams having a wide variety of QOSs. In addition, where the speed (or bandwidth) of components varies within a given data path through a network, the traffic being transmitted from the faster components may need to be throttled to prevent jamming of the slower components with more data traffic than they can handle.
The network component most responsible for maintaining the QOSs, transmission rates, etc. of the various communication streams exiting a node is the "transmit side" of the NIC. On the NIC's transmit side, a transmit scheduling mechanism (or "scheduler") is needed which can meter simultaneously a large number of data streams into a network such that the QOS specified for each stream can be maintained end-to-end by the network.
The most common transmit schedulers employed in recent communication networks are rate queues. There are a variety of rate queue implementations, most of which are found in asynchronous transfer mode (ATM) NICs. Rate queues range from very simple circuits that can handle only a few streams simultaneously to fairly complex circuits that can manage thousands of channels (or VCs) simultaneously, with a maximum of a few hundred active at any given time.
A rate queue is typically implemented as a free-running circular buffer or re-circulating FIFO (first-in-first-out), wherein each location in the queue represents a fixed-size time slot. A channel is assigned to a particular time slot through the insertion of the appropriate channel number into the slot. The total number of time slots in a queue can be varied to alter the frequency in which each queue entry is accessed. The number of queue entries assigned a particular channel can be varied to alter the number of data elements transmitted over the channel during one pass through the queue. In some rate queue implementations, the time represented by each time slot can be varied somewhat to alter the base rate and the total time represented by one pass through the queue.
There are a number of drawbacks to rate queues which make them inadequate for handling simultaneously a large number of communication channels with diverse characteristics. First, the granularity of rates available for streams are generally limited in rate queues to some function of the time it takes to transmit a fixed-size data element at the maximum rate of the NIC output. For instance, the time it takes to transmit an ATM cell over an OC-3 SONET link is about 2.8 microseconds. Many rate queues on ATM/OC-3 NICs can only produce transmission rates that are some function of an integral number of these 2.8 microsecond time slots. More sophisticated rate queues can produce transmission rates that are some harmonic of the NIC clock cycle time, but even this granularity may be inadequate for the mix of communication streams in some networks.
A second drawback to rate queues is that they can generally handle only a few different transmission base rates simultaneously, with each base rate assigned to a different rate queue. All transmission rates must then be some function of these few base rates. Because each rate queue requires a separate set of data storage locations and separate control logic, the total number of queues (and thus the total number of base rates) implemented by a particular NIC is limited by the practicalities of the hardware requirements. In addition, if a given rate queue were implemented to handle the large number of voice channels (with slow transmission rates and minimal bandwidth requirements) that potentially could be active simultaneously on a given high speed network link, a large amount of hardware would be required, even though much of it would likely be wasted most of the time.
Yet another drawback to rate queues is that they can handle only a limited mixture of traffic types (transmission rates, QOSs, etc.), due to the fixed nature of the characteristics of each queue. The simultaneous management of rate queues entries for a wide variety of traffic types with diverse QOSs over a large number of channels is difficult to do in a way that ensures the link bandwidth is used efficiently and the QOSs are maintained.
An alternative to rate queues for transmit scheduling is described in U.S. Pat. No. 5,579,302, issued Nov. 26, 1996 to Banks (the "'302 patent"). However, the "guaranteed bandwidth scheduler" of the '302 patent is designed specifically for data traffic having a constant frame size and a constant stride (e.g., CBR data), such as is used in asynchronous transfer mode (ATM) network applications. Because the data transmission scheduling calculations for a particular VC, according to the '302 patent, are performed based upon constant frame sizes and strides, the worst case bandwidth requirement (i.e., the maximum frame size and frame stride) must be assumed when scheduling non-CBR (such as, e.g., Ethernet) data traffic. Thus, if the average data frame size and/or stride for a particular VC are lower than the maximum possible for that VC, bandwidth may be wasted.
A further drawback of the scheduler of the '302 patent is the lack of a predetermined set of steps (i.e., a predetermined time period) for the scheduling of the next data transmission for a particular VC. It is possible that a scheduler, in attempting to select a time slot for the next data transmission for a particular VC, will find that the time slot has already been assigned to another VC. Thus, a conflict resolution mechanism, which attempts to find an alternative time slot for one of the conflicting VCs, may be employed. Conflict resolution according to the '302 patent scheduler is an unbounded iterative process, which could potentially cause significant delays in scheduling or even an unrecoverable loss of time, and thus introduce a high amount of error into one or more of the VC data streams. The likelihood of conflicts between VCs being scheduled and, thus, the likelihood of the introduction of significant delays or the unrecoverable loss of time, can be reduced in the '302 patent scheduler by minimization of the number of possible simultaneously active VCs allowed in relation to the number of total possible transmission time slots. This leads, however, to underutilization of the available time slots, and thus an inefficient use of the available bandwidth.